480C - Riding in a Lift - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=5010,mod=1e9+7;
int T,n,a,b,k;  //第i次在j位置的方案数
void add(int a,int b,int c,int diff[]){ //区间[a,b)
    diff[a]=(diff[a]+c)%mod;
    diff[b]=(diff[b]-c+mod)%mod;
}
void solve(){
    cin>>n>>a>>b>>k;
    int diff[n+2];  //差分数组  x到y的范围为(x-d,x+d) 因此可以使用差分数组记录方案数
    memset(diff,0,sizeof diff);
    add(a,min(a+1,n+1),1,diff);  //起点初始化
    for(int i=1;i<=k;i++){
        vector<int>s(n+1,0);
        for(int j=1;j<=n;j++){
            s[j]=(s[j-1]+diff[j])%mod;
        }
        memset(diff,0,sizeof diff);  //初始化 清空上一轮的状态(不清空结果不对)
        for(int j=1;j<=n;j++){
            int d=abs(j-b);
            int l=max(1,j-d+1),r=min(n+1,j+d);
            //cout<<l<<" "<<r<<" "<<j<<" "<<s[j]<<endl;
            add(l,j,s[j],diff);   //不能停在原点 因此分成两部分计算
            add(j+1,r,s[j],diff);
        }
    }
    ll res=0,pre=0;
    for(int i=1;i<=n;i++){  //统计终点在[1,n]的方案数
       pre=(pre+diff[i]+mod)%mod;
       res=(res+pre)%mod;
       //cout<<diff[i]<<" ";
    }
    cout<<res<<endl;
}
int main(){
    T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}